package 高级班;

public class Problem01_MinBoat {

    // 请保证arr有序
    public static int minBoat(int[] arr, int weight) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int lessR = -1;
        for (int i = arr.length - 1; i >= 0; i--) {
            if (arr[i] <= (weight / 2)) {
                lessR = i;
                break;
            }
        }
        if (lessR == -1) {
            return arr.length;
        }
        int lessIndex = lessR;
        int moreIndex = lessR + 1;
        int lessUnused = 0;
        while (lessIndex >= 0) {
            int solved = 0;
            while (moreIndex < arr.length
                    && arr[lessIndex] + arr[moreIndex] <= weight) {
                moreIndex++;
                solved++;
            }
            if (solved == 0) {
                lessUnused++;
                lessIndex--;
            } else {
                lessIndex = Math.max(-1, lessIndex - solved);
            }
        }
        int lessAll = lessR + 1;
        int lessUsed = lessAll - lessUnused;
        int moreUnsolved = arr.length - lessR - 1 - lessUsed;
        return lessUsed + ((lessUnused + 1) >> 1) + moreUnsolved;
    }

    public static int minBoat_ytc(int[] arr,int weight){
        if (arr.length==0||arr==null)
            return 0;
        int lessR=-1;
        for (int i=arr.length-1;i>=0;i--){
            if (arr[i]<=(weight/2)){
                lessR=i;
                break;
            }
        }
        if (lessR==-1)
            return arr.length;
        int lessindex=lessR;
        int moreindex=lessR+1;
        int lessUnused=0;
        while (lessindex>=0){
            int solve=0;
            while (moreindex<arr.length&&arr[lessindex]+arr[moreindex]<=weight){
                moreindex++;
                solve++;
            }
            if (solve==0){
                lessindex--;
                lessUnused+=1;
            }else {
                lessindex=Math.max(-1,lessindex-solve);
            }
        }
        int lessAll=lessR+1;
        int lessUsed=lessAll-lessUnused;
        int moreUnused= arr.length-(lessR+1)-lessUsed;
        return lessUsed+((lessUnused+1)>>1)+moreUnused;
    }

    public static void main(String[] args) {
        int[] arr = { 1, 2, 2, 2, 2, 4, 4, 4, 4, 5 };
        int weight = 5;
        System.out.println(minBoat(arr, weight));
        System.out.println(minBoat_ytc(arr,weight));
    }

}
